package midalgorithms.dynamicplanning;

public class _04LengthOfLIS {
    public static int lengthOfLIS(int[] nums) {
        //  动态规划
        //  dp[i]表示从nums[0]到nums[i]的序列中最长子序列的长度
        //  难点就在于找到dp[i]和之前各项的关系！
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int res = 1;
        for (int i = 1;i < nums.length;i++){
            int max = 0;
            for (int j = 1;j <= i;j++){
                if(nums[i] > nums[i - j]){
                    //  不断和前面的比较，大于则取其中的最大值
                    max = Math.max(dp[i - j], max);
                }
            }
            //  取出最大值+1，就是这个位置的dp值
            dp[i] = max + 1;
            if(dp[i] > res){
                res = dp[i];
            }
        }
        return res;
    }
}
